package tree;

import java.util.TreeMap;

public class Trie {


    private class Node{
        public boolean isWord;  //标识单词是否结束
        public TreeMap<Character, Node> next;


        public Node(boolean isWord){
            this.isWord = isWord;
            next = new TreeMap<>();
        }

        public Node(){
            this(false);
        }
    }

    private Node root;
    private int size;

    public Trie(){
        root = new Node();
        size = 0;
    }

    public int getSize(){
        return size;
    }

    //想Trie中添加单词
    public void add(String word){
        if(word == null){
            throw new IllegalArgumentException("Word is Illegal");
        }


        Node cur = root;
        for (int i = 0; i < word.length(); i++) {
            char c = word.charAt(i);
            if(cur.next.get(i) == null){
                //需要创建一个新节点
                cur.next.put(c,new Node());
            }
            cur = cur.next.get(c);
        }

        // !cur.isWord：判断这个单词之前是否就已经存在
        if(!cur.isWord){
            //循环到最后，代表单词已经添加完毕
            cur.isWord = true;
            size++;

        }

    }

    //递归实现
    private Node add(Node node, String word){

        return null;
    }

    //查询单词是否存在
    public boolean contains(String word){
        Node cur = root;

        for (int i = 0; i < word.length(); i++) {
            char c = word.charAt(i);
            if(cur.next.get(c) == null){
                return false;
            }
            cur = cur.next.get(c);
        }

        //来到字符串最后一个节点
        return cur.isWord;
    }

    /**
     * 查询在Trie中是否有单词以prefix为前缀
     * @param prefix：指定前缀
     * @return
     */
    public boolean isPrefix(String prefix){

        Node cur = root;
        for (int i = 0; i < prefix.length(); i++) {
            char c = prefix.charAt(i);
            if(cur.next.get(c) == null){
                return false;
            }
            cur = cur.next.get(c);
        }

        return true;
    }


    public void addWord(String word){
        //遍历添加
        Node cur = root;
        for (int i = 0; i < word.length(); i++) {
           char c = word.charAt(i);
           if(cur.next.get(c) == null){
               //添加节点
               cur.next.put(c,new Node());
           }
            cur = cur.next.get(c);
        }

        cur.isWord = true;

    }

    //正则匹配，.代表任意字符
    public boolean search(String word){
        boolean isMatch = match(root,word,0);
        return isMatch;
    }

    // 递归匹配
    private boolean match(Node node, String word, int index){
        if(index == word.length()){
            return node.isWord;
        }

        char c = word.charAt(index);
        if(c != '.'){
            if(node.next.get(c) == null){
                return false;
            }
            return match(node.next.get(c) , word , index+1);
        }else {
            //如果c == . ,那就需要遍历所有的子节点
            for(char nextChar: node.next.keySet()){
                if(match(node.next.get(nextChar), word , index + 1)){
                    return true;
                }
            }

            return false;
        }
    }

    //递归添加
//    private void addWord(Node node,char c, int index){
//
//        if(node.next.get(c) == null){
//            //新增一个node
//            node.next.put(c,new Node());
//            size++;
//            node.next.get(c).isWord = true;
//            return;
//        }
//
//        //包含有这个字符，那就继续调用
//        addWord(node.next.get(c),c);
//
//    }


}
